import javafx.util.Pair;

import java.io.PrintWriter;
import java.util.*;

//优先级队列_前 K 个高频单词
//https://leetcode.cn/problems/top-k-frequent-words/description/

//自定义一个pair类
/*class Pair<K, V> {
    private final K key;
    private final V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    @Override
    public String toString() {
        return "Pair{" +
                "key=" + key +
                ", value=" + value +
                '}';
    }
}*/


public class Test {
    public static void main(String[] args) {

    }
}


class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //1.统计字符串的出现次数
        Map<String,Integer> map = new HashMap<>();
        for(String key : words){
            map.put(key,map.getOrDefault(key,0)+1);
        }

        //2.创建大小为K的小根堆
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
                (a,b) ->
                {
                    //.equals——这种写法也可以
                    if(a.getValue() == (b.getValue())){//注意这里的写法：频次相同的时候，字典序按照大根堆的方式排列
                        return b.getKey().compareTo(a.getKey());//还有这里的顺序,不能颠倒！！！具体原因要看看
                    }
                    return a.getValue() - b.getValue();
                }
        );

        //3.遍历哈希表，让pair对进堆
        /*//编译器版本不同，这个小写的不行
        for(Map.entry<String,Integer> e : map.entrySet()){

        }*/
        for(Map.Entry<String,Integer> entry : map.entrySet()){//这里的写法、用法，要熟悉
            heap.offer(new Pair<>(entry.getKey(),entry.getValue()));
            if(heap.size() > k){
                heap.poll();
            }

        }

        ///4.提取单词
        List<String> res = new ArrayList<>();
        while(!heap.isEmpty()){
            res.add(heap.poll().getKey());
        }
        Collections.reverse(res);
        return res;
    }
}